from timeit import Timer

import sys
import math


def Problem():
    """A permutation is an ordered arrangement of objects. 
    For example, 3124 is one possible permutation of the digits 
    1, 2, 3 and 4. If all of the permutations are listed numerically 
    or alphabetically, we call it lexicographic order. The 
    lexicographic permutations of 0, 1 and 2 are:

    012   021   102   120   201   210

    What is the millionth lexicographic permutation of the digits 
    0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
    """
    
    
    permutation = []
    
    def Permutate(k, s):
        n, factorial = len(s), 1;
        s = list(s)
        
        # compute (n- 1)!
        for j in range(2, n): 
            factorial *= j
        
        #Is number in range [0, len(s)! - 1]
        if k / n >= factorial:
            return ""
            
        # for j= 1 to n- 1 
        for j in range(0, n - 1):
            # tempj:= (k/ factorial) mod (n - j);
            # temps:= s[j+ tempj]
            # for i= (j+ tempj) to (j+ 1) step -1 {
            #     s[i]:= s[i- 1];      // shift the chain right
            # }
            # s[j]:= temps;
            # factorial:= factorial/ (n- j);

            
            tempj = (k // factorial) % (n - j)
            temps = s.pop(j + tempj)
            s.insert(j, temps)

            factorial = factorial / (n - (j + 1))

        return s;

    result = Permutate(10**6-1, "0123456789")
    ans = "".join(result)
    
    print "Answer for Problem 24 = %s " % (ans,)


    
if __name__ == "__main__":
    t = Timer(setup='from __main__ import Problem', stmt='Problem()').timeit(1)
    print "Execution time = %0.3f seconds" %(t,)